package d2;
import java.util.*;
public class Day8 {
    public static void main(String[] args) {
//        String s = "bbbbbb";
//        StringBuilder tmp = new StringBuilder(s);
//        String ss = tmp.replace(0,0+1,"a").toString();
//        System.out.println(tmp);
        String[] a = {"AACCGGTA","AACCGCTA","AAACGGTA"};

        //minMutation("AACCGGTT","AAACGGTA",a);
    }
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) return 0;//优化1
        Set<String> set = new HashSet<>();
        for(String s:bank) set.add(s);
        if(!set.contains(endGene)) return -1;//优化2
        Set<String> vis = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        char[] ck = {'A','C','G','T'};//优化3
        queue.add(startGene);
        int ret=0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            ret++;
            for(int i=sz;i>0;i--) {
                String t = queue.poll();
                if(t.equals(endGene)) return ret;
                vis.add(t);
                for(int j=0;j<8;j++) {
                    //每次改变一个字符，并查看是否在基因库中和不在vis中(不在证明没有被搜索过)
                    StringBuilder tmp = new StringBuilder(t);
                    for(int k=0;k<4;k++) {//优化3
                        String str = tmp.replace(j,j+1,ck[k]+"").toString();
                        if(str.equals(endGene)) return ret;
                        if(set.contains(str) && !vis.contains(str)) {
                            queue.add(str);
                            vis.add(str);
                        }
                    }
                }
            }
        }
        return -1;
    }




    public static int minMutations(String startGene, String endGene, String[] bank) {
        Set<String> set = new HashSet<>();
        for(String s:bank) set.add(s);
        Set<String> vis = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        int ret=0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            ret++;
            for(int i=sz;i>0;i--) {
                String t = queue.poll();
                if(t.equals(endGene)) return ret;
                vis.add(t);
                for(int j=0;j<t.length();j++) {
                    //每次改变一个字符，并查看是否在基因库中和不在vis中(不在证明没有被搜索过)
                    StringBuilder tmp = new StringBuilder(t);
                    StringBuilder A = tmp;
                    String AA = A.replace(j,j+1,"A").toString();
                    if(set.contains(AA) && !vis.contains(AA)) {
                        if(AA.equals(endGene)) return ret;
                        queue.add(AA);
                        vis.add(AA);
                    }
                    StringBuilder C = tmp;
                    String CC = C.replace(j,j+1,"C").toString();
                    if(set.contains(CC) && !vis.contains(CC)) {
                        if(CC.equals(endGene)) return ret;
                        queue.add(CC);
                        vis.add(CC);
                    }
                    StringBuilder G = tmp;
                    String GG = G.replace(j,j+1,"G").toString();
                    if(set.contains(GG) && !vis.contains(GG)) {
                        if(GG.equals(endGene)) return ret;
                        queue.add(GG);
                        vis.add(GG);
                    }
                    StringBuilder T = tmp;
                    String TT = T.replace(j,j+1,"T").toString();
                    if(set.contains(TT) && !vis.contains(TT)) {
                        if(TT.equals(endGene)) return ret;
                        queue.add(TT);
                        vis.add(TT);
                    }
                }
            }
        }
        return -1;
    }


}
